#!/usr/bin/env python
# -*- coding: utf-8 -*-

def partition(arr, first, last):
    key = arr[first];
    lp = first + 1;
    rp = last;
    while lp <= rp:
        while lp <= rp and arr[lp] <= key:
            lp += 1;
        while lp <= rp and arr[rp] >= key:
            rp -= 1;
        if lp < rp:
            arr[lp], arr[rp] = arr[rp], arr[lp];
    arr[first], arr[rp] = arr[rp], arr[first];
    return rp;

def sort(arr, first, last):
    if first < last:
        splitpoint = partition(arr, first, last);
        sort(arr, first, splitpoint-1);
        sort(arr, splitpoint+1, last);

def quick_sort(arr):
    return sort(arr, 0, len(arr)-1);

def main():
#     arr = [9, 2, 1, 7, 6, 8, 5, 3, 4];
    arr = [54,26,93,17,77,31,44,55,20];
    quick_sort(arr);
    print arr;
    
if __name__ == '__main__':
    main();